import java.util.*;

/**
 * Creat with IntelliJ IDEA
 * Description:
 * User:WZW
 * Date:2022-03-06
 * Time:23:59
 */
public class OJ_3_5 {

     public class ListNode {
         int val;
         ListNode next;

         ListNode(int x) {
             val = x;
         }
     }

    /**
     * 剑指 Offer 06. 从尾到头打印链表
     * 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
     * @param head
     * @return
     */
    public int[] reversePrint(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode cur = head;
        while(cur != null){
            stack.push(cur.val);
            cur = cur.next;
        }
        int[] ret = new int[stack.size()];
        int i = 0;
        while(!stack.isEmpty()){
            ret[i++] = stack.pop();
        }
        return ret;
    }

    /**
     * 剑指 Offer 24. 反转链表
     * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        if(head == null) return null;
        ListNode cur = head;
        ListNode prev = null;
        ListNode curNext = cur.next;
        while(cur != null)
        {
            cur.next = prev;
            prev = cur;
            cur = curNext;
            if(cur != null){
                curNext = cur.next;
            }
        }
        return prev;
    }

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    /**
     * 剑指 Offer 35. 复杂链表的复制
     * 请实现 copyRandomList 函数，复制一个复杂链表。
     * 在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
     * @param head
     * @return
     */

    public Node copyRandomList(Node head) {
        if(head == null) return null;
        HashMap<Node,Node> map = new HashMap<>();
        Node cur = head;
        while(cur != null)
        {
            Node tmp = new Node(cur.val);
            map.put(cur,tmp);
            cur = cur.next;
        }
        cur = head;
        while(cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }

    /**
     * 剑指 Offer 05. 替换空格
     * 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
     * @param s
     * @return
     */
    public String replaceSpace(String s) {
        StringBuilder str = new StringBuilder();
        for (int i = 0; i <s.length() ; i++) {
            char c = s.charAt(i);
            if (c==' '){
                str.append("%20");
            }else {
                str.append(c);
            }
        }
        return str.toString();
    }

    /**
     * 剑指 Offer 58 - II. 左旋转字符串
     * 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。
     * 请定义一个函数实现字符串左旋转操作的功能。
     * 比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
     * @param s
     * @param n
     * @return
     */
    public String reverseLeftWords(String s, int n) {
        if(n > s.length()) {
            n %= s.length();
        }
        StringBuilder ss = new StringBuilder();
        ss.append(s,n,s.length());
        ss.append(s,0,n);
        return ss.toString();
    }

    /**
     * 剑指 Offer 03. 数组中重复的数字
     * https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
     * 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。
     * 数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
     * 请找出数组中任意一个重复的数字。
     * @param nums
     * @return
     */
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int n:nums){
            if(set.contains(n))
            {
                return n;
            }else
            {
                set.add(n);
            }
        }
        return -1;
    }

    /**
     * 剑指 Offer 53 - I. 在排序数组中查找数字 I
     * https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
     * 统计一个数字在排序数组中出现的次数。
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        int count =0;
        for(int n:nums)
        {
            if(n==target){
                count++;
            }
        }
        return count;
    }

    /**
     * 剑指 Offer 53 - II. 0～n-1中缺失的数字
     * https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/
     *
     * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。
     * 在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
     *
     * 思路1：创建一个数组，如果一样就删除，最后剩下一个数
     * 思路2：异或，最后剩下的就是答案
     * @param nums
     * @return
     */
    public int missingNumber(int[] nums) {
        int size = nums.length;
        int n = 0;
        for(int i =0; i <= size;i++)
        {
            n ^= i;
        }
        for(int i:nums)
        {
            n ^= i;
        }
        return n;
    }

    /**
     * 剑指 Offer 04. 二维数组中的查找
     * https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
     * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
     * 请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
     * @param matrix
     * @param target
     * @return
     */
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) return false;
        int i = 0;
        int j = matrix[0].length - 1;
        while(i < matrix.length && j >= 0){
            if (target < matrix[i][j]){
                j--;
            }else if (target > matrix[i][j]){
                i++;
            }
            else {
                return true;
            }
        }
        return false;
    }

    /**
     * 剑指 Offer 11. 旋转数组的最小数字
     * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
     * https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
     * 给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。
     * 请返回旋转数组的最小元素。
     * 例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为1。
     * @param numbers
     * @return
     */
    public int minArray(int[] numbers) {
        int i = 0;
        int j = numbers.length-1;
        int m = (i+j)>>1;
        while (i<j){
            if (numbers[m] > numbers[j]){//numbers[m]不可能是最小值
                i = m + 1;
            }else if (numbers[m] < numbers[j]) {//numbers[m]可能是最小值
                j = m;
            }else {
                j--;
            }
            m = (i+j)>>1;
        }
        return numbers[i];
    }

    /**
     * 面试题50. 第一个只出现一次的字符
     * https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/
     * 在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
     * @param s
     * @return
     */
    public char firstUniqChar(String s) {
        HashMap<Character,Boolean> map = new HashMap<>();
        for (Character c: s.toCharArray()) {
            if (map.containsKey(c)){
                map.put(c,false);
            }else {
                map.put(c,true);
            }
        }
        for (Character c: s.toCharArray()) {
            if (map.get(c) == true) {
                return c;
            }
        }
        return ' ';
    }

     public class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode(int x) {
             val = x;
         }
     }

    /**
     * 面试题32 - I. 从上到下打印二叉树
     * https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
     * 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
     * @param root
     * @return
     */
    public int[] levelOrder1(TreeNode root) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        if (root == null)return new int[0];
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            while (size!=0){
                TreeNode tmp = queue.poll();
                arrayList.add(tmp.val);
                if (tmp.left != null){
                    queue.offer(tmp.left);
                }
                if (tmp.right != null){
                    queue.offer(tmp.right);
                }
                size--;
            }
        }
        int[] ret = new int[arrayList.size()];
        for (int i = 0; i< arrayList.size(); i++){
            ret[i] = arrayList.get(i);
        }
        return ret;
    }

    /**
     * 剑指 Offer 32 - II. 从上到下打印二叉树 II
     * https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/
     * 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root ==null) return list;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> subList = new ArrayList<>();
            while (size != 0){
                TreeNode tmp = queue.poll();
                subList.add(tmp.val);
                if (tmp.left!=null){
                    queue.offer(tmp.left);
                }
                if (tmp.right!=null){
                    queue.offer(tmp.right);
                }
                size--;
            }
            list.add(subList);
        }
        return list;
    }

    /**
     * 剑指 Offer 32 - III. 从上到下打印二叉树 III
     * https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
     * 请实现一个函数按照之字形顺序打印二叉树，
     * 即第一行按照从左到右的顺序打印，
     * 第二层按照从右到左的顺序打印，
     * 第三行再按照从左到右的顺序打印，其他行以此类推。
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root ==null) return list;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> subList = new ArrayList<>();
            while (size != 0){
                TreeNode tmp = queue.poll();
                subList.add(tmp.val);
                if (tmp.left!=null){
                    queue.offer(tmp.left);
                }
                if (tmp.right!=null){
                    queue.offer(tmp.right);
                }
                size--;
            }
            if (list.size() % 2 == 1){
                Collections.reverse(subList);
            }
            list.add(subList);
        }
        return list;
    }

    /**
     * 剑指 Offer 26. 树的子结构
     * https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/
     * 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
     *
     * B是A的子结构， 即 A中有出现和B相同的结构和节点值。
     * @param A
     * @param B
     * @return
     */
    public boolean isSameStructure(TreeNode A,TreeNode B){
        if (A == null && B == null) {
            return true;
        }
        if (A == null)return false;
        if (B == null)return true;
        if (A.val!=B.val) return false;
        if (isSameStructure(A.left,B.left) == false) return false;
        return isSameStructure(A.right,B.right);
    }

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A==null || B == null) return false;
        if (isSameStructure(A,B)==true) return true;
        if (isSubStructure(A.left,B) == true) return true;
        return isSubStructure(A.right,B);
    }

    /**
     * 剑指 Offer 27. 二叉树的镜像
     * https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/
     * 请完成一个函数，输入一个二叉树，该函数输出它的镜像。
     * @param root
     * @return
     */
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) return null;
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        mirrorTree(root.left);
        mirrorTree(root.right);
        return root;
    }

    /**
     * 剑指 Offer 28. 对称的二叉树
     * https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/
     * 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
     * @param root
     * @return
     */

    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isSymmetricTree(root.left,root.right);
    }

    public boolean isSymmetricTree(TreeNode l,TreeNode r){
        if (l == null && r == null) return true;
        if (l == null || r == null) return false;
        if (l.val != r.val) return false;
        if (isSymmetricTree(l.left,r.right)==false) return false;
        return isSymmetricTree(l.right,r.left);
    }

    /**
     * 剑指 Offer 10- I. 斐波那契数列
     * 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
     *
     * F(0) = 0,   F(1) = 1
     * F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
     * 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
     *
     * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
     *
     *
     */
    public int fib(int n) {
        if (n<2) return n;
        int a = 0;
        int b = 1;
        for (int i = 2; i <= n; i++) {
            int tmp = (a+b)%1000000007;
            a = b;
            b = tmp;
        }
        return b;
    }

    /**
     * 剑指 Offer 10- II. 青蛙跳台阶问题
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
     *
     * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
     * @param n
     * @return
     */
    public int numWays(int n) {
        int[] num = new int[101];
        num[0]=1;
        num[1]=1;
        for (int i = 2; i <=n ; i++) {
            num[i]=(num[i-1]+num[i-2])%1000000007;
        }
        return num[n];
    }

    /**
     * 剑指 Offer 63. 股票的最大利润
     * 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
     * https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            max = Math.max(max,prices[i]-prices[i-1]);
            prices[i] = Math.min(prices[i],prices[i-1]);
        }
        return max;
    }
}
